/* 给你很多形如[start,end]的闭区间
 * 请你设计一个算法
 * 算出这些区间中最多有几个互不相交的区间。
 */
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class intervals {
public:
    int intervalSchedule(vector<pair<int, int> >& intvs) {
        if (intvs.size() == 0)
            return 0;
        // 按区间的end升序排列
        sort(intvs.begin(), intvs.end(), my_comp);
        // 至少有一个区间
        int count = 1;
        // 排序后获得区间x
        int x_end = intvs[0].second;
        for (vector<pair<int, int> >::iterator interval = intvs.begin(); interval != intvs.end(); interval++) {
            int start = interval->first;
            if (start >= x_end) {
                // 更新x
                count++;
                x_end = interval->second;
            }
        }

        return count;
    }

    static bool my_comp(pair<int, int>& p1, pair<int, int>& p2) {
        return p1.second < p2.second;
    }
};

class intervalsTest {
public:
    int intervawlSchedule(vector<pair<int, int> >& intvs) {
        if (intvs.size() == 0)
            return 0;
        sort(intvs.begin(), intvs.end(), [](pair<int, int> &p1, pair<int, int> &p2) -> bool {
            return v1.second < v2.second;
        });
        int count = 1;
        int x_end = intvs[0].second;
        for (auto &interval : intvs) {
            int start = interval.first;
            if (start >= x_end) {
                count++;
                x_end = interval.second;
            }
        }

        return count;
    }
};

// 最小重叠子区间
class eraseIntervals {
public:
    int eraseOverlapIntervals(vector<vector<int> >& intervals) {
        if (intervals.size() == 0)
            return 0;
        
        sort(intervals.begin(), intervals.end(), [](auto& v1, auto& v2) {
            return v1[1] < v2[1];
        });
        int x_end = intervals[0][1];
        int count = 1;
        int n = intervals.size();
        for (int i = 0; i < n; i++) {
            if (intervals[i][0] >= x_end) {
                count++;
                x_end = intervals[i][1];
            }
        }

        return n - count;
    }
};

// 刺破气球最少的箭头
class minArrows {
public:
    int findMinArrowShots(vector<vector<int> >& points) {
        if (points.size() == 0)
            return 0;
        sort(points.begin(), points.end(), [](auto& p1, auto&p2) {
            return p1[1] < p2[1];
        });
        int count = 1;
        int n = points.size();
        int x_end = points[0][1];
        for (int i = 1; i < n; i++) {
            if (points[i][0] > x_end) {
                count++;
                x_end = points[i][1];
            }
        }

        return count;
    }
};

// jump game I
class jumpOne {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int farthest = 0;
        // 每次更新可以跳到最远的地方，看最后是否超过最后下标
        for (int i = 0; i < n - 1; i++) {
            farthest = max(farthest, i + nums[i]);
            if (farthest <= i)
                // 跳不动了 <= 0
                return false;
        }

        return farthest >= n - 1;
    }
};

// jump game II
// 最少次数跳到末尾
class dpJumpTwo {
    vector<int> memo;
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        memo = vector<int>(n, n);
        return dp(nums, 0);
    }

    int dp(vector<int>& nums, int p) {
        int n = nums.size();

        if (p >= n - 1) 
            return 0;
        
        if (memo[p] != n)
            return memo[p];
        
        int steps = nums[p];
        for (int i = 1; i <= steps; i++) {
            int subProblem = dp(nums, p + i);
            memo[p] = min(memo[p], subProblem + 1);
        }
        return memo[p];
    }
};
// dpTable
class dpTableJumpTwo {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int dp[n];
        for (int i = 0; i < n; i++)
            dp[i] = n;
        dp[n - 1] = 0;

        for (int i = n - 2; i >= 0; i--) {
            int steps = nums[i];
            for (int step = 1; step <= steps; step++) {
                if (i + step >= n - 1)
                    dp[i] = 1;
                else 
                    dp[i] = min(dp[i], dp[i + step] + 1);
            }
        }

        return dp[0];
    }
};

// 贪心法
// i和end标记了可以选择的跳跃步数
// farthest标记了所有可选择跳跃步数[i..end]中能够跳到的最远距离
// jumps记录了跳跃次数
class greedyJumpTwo {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int end = 0, farthest = 0;
        int jumps = 0;
        for (int i = 0; i < n - 1; i++) {
            farthest = max(nums[i] + i, farthest);
            if (end == i) {
                jumps++;
                end = farthest;
            }
        }
        return jumps;
    }
};